package interview.huawei.tjt.training.dongtaiguihua;

import java.util.Scanner;

/**
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 *
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * 改为：一步一个台阶，两个台阶，三个台阶，.......，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？
 *
 * 注意：给定 n 是一个正整数。
 *
 * 示例 1： 输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。
 *
 * 1 阶 + 1 阶
 * 2 阶
 * 示例 2： 输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。
 *
 * 1 阶 + 1 阶 + 1 阶
 * 1 阶 + 2 阶
 * 2 阶 + 1 阶
 */
public class ClimbStairsII {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入可以跨的台阶种类：");
        int m = scanner.nextInt();
        System.out.println("请输入需要爬的台阶阶数：");
        int target = scanner.nextInt();
        int[] nums = new int[m];
        for (int i = 0; i < m; i ++) {
            nums[i] = i + 1;
        }
        int[] dp = new int[target + 1];
        dp[0] = 1;
        // 因为 1 + 2阶 和 2 + 1阶是两种不同的方式，因此采用排列的方式，即先遍历背包再遍历物品
        // 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
        // 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
        // 背包从前往后遍历是为了使每个物品可以多次放入
        for (int i = 0; i <= target; i ++) {
            for (int j = 0; j < nums.length; j ++) {
                if ( i >= nums[j] ) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        System.out.println("到达" + target + "阶的方法种类为：");
        System.out.println(dp[target] + " 种");
    }

}
